package linear_list.leetcode.medium;

/**
 * @author Stark
 * @description 给定一个链表,如果链表有环，返回开始入环的第一个节点，否则返回null
 * 题目链接：https://leetcode-cn.com/problems/linked-list-cycle-ii
 * @date 2022/4/9 15:54
 **/
public class Num142_DetectCycle {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null)
            return null;
        ListNode fast = head,slow = head;
        while(true){
            if(fast == null || fast.next == null)
                return null;
            fast = fast.next.next;
            slow = slow.next;
            //当快慢指针相遇后，再从定义一个从头开始走的索引
            //和慢指针一起每次移动一步,他们肯定会在入环结点相遇
            //快指针路程 fL ,慢指针路程 sL ,非环状结点数 a, 环状结点数 b
            //fL = 2 * sL,fL = n*b + sL
            //解得fL = 2*n*b,sL = n*b
            //再次从头结点出发的路程：a ，慢指针走的路程：a + nb
            //慢指针只是多走了环状结点的n倍,所以两者一定会相遇
            if(fast == slow){
                ListNode cur = head;
                while(cur != slow){
                    cur = cur.next;
                    slow = slow.next;
                }
                return cur;
            }
        }
    }
}
